package com.lihui.heapsort;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/11/07  11:01
 */
public class HeapSort {
    public static void createHeap(int[] array){

        for (int parent = (array.length - 2) / 2; parent >= 0; parent--) {

            shiftDown (array, parent, array.length);
        }
    }

    private static void shiftDown(int[] array, int parent, int length) {
        int child = parent * 2 + 1;
        while (child < length){
            if(child + 1 < length){
                if(array[child + 1] > array[child]){
                    child++;
                }
            }
            if(array[child] <= array[parent]){
                break;
            }
            swap(array,parent,child);
            parent = child;
            child = parent * 2 + 1;
        }
    }

    private static void swap(int[] array, int parent, int child) {
        int temp = array[parent];
        array[parent] = array[child];
        array[child] = temp;
    }

    public static void sort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while (end >= 0){
            swap(array,0,end);
            shiftDown(array,0,end );
            end--;
        }
    }

    public static void main(String[] args) {
        int [] array = { 27,15,19,18,28,34,65,49,25,37 };
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}
